#include <stdio.h>
#include "common.h"

int BubbleSort(int *buff, int buff_len)
{
	int i = 0, j = 0;
	int tmp = 0;

	if (buff == NULL || buff_len <= 0)
	{
		return PARAMETER_ERROR;
	}

	for (i = 0; i < buff_len - 1; i++)
	{
		for (j = 0; j < buff_len - 1 - i; j++)
		{
			if (buff[j] > buff[j + 1])
			{
				tmp = buff[j];
				buff[j] = buff[j + 1];
				buff[j + 1] = tmp;
			}
		}
	}
	return 0;
}

int InsertSort(int *buff, int buff_len)
{
	int i = 0, j = 0;
	int tmp = 0;

	if (buff == NULL || buff_len <= 0)
	{
		return PARAMETER_ERROR;
	}

	// 一共需要len-1轮
	for (i = 1; i < buff_len; i++)
	{
		// buff[0]~buff[i-1]是有序的，
		// 但buff[0]~buff[i]不是有序的。
		if (buff[i] < buff[i - 1])
		{
			// 如果buff[i]小于buff[i - 1]就需要插入
			tmp = buff[i];
			buff[i] = buff[i - 1]; // 移动一个
			for (j = i - 2; (j >= 0 && tmp < buff[j]); j--)
			{
				buff[j + 1] = buff[j];
			}
			buff[j + 1] = tmp;
		}
	}

	return 0;
}

int SelectSort(int *buff, int buff_len)
{
	int i = 0, j = 0;
	int index = 0;
	int tmp = 0;

	if (buff == NULL || buff_len <= 0)
	{
		return PARAMETER_ERROR;
	}

	// buff_len-1轮
	for (i = 0; i < buff_len - 1; i++)
	{
		index = i;
		// 选出一个最小（升序）/最大（降序）的与buff[i-1]交换位置
		for (j = i + 1; j < buff_len; j++)
		{
			if (buff[j] < buff[index])
			{
				index = j;
			}
		}
		tmp = buff[index];
		buff[index] = buff[i];
		buff[i] = tmp;
	}

	return 0;
}

static int GetIndex(int *buff, int low, int high)
{
	int tmp = 0;

	tmp = buff[low];

	while (low < high)
	{
		while (low < high && buff[high] >= tmp)
		{
			high--;
		}
		buff[low] = buff[high];
		while (low < high && buff[low] <= tmp)
		{
			low++;
		}
		buff[high] = buff[low];
	}
	buff[low] = tmp;
	return low;
}

static void do_QuickSort(int *buff, int low, int high)
{
	int index = 0;

	if (low >= high)
	{
		return;
	}

	index = GetIndex(buff, low, high);
	do_QuickSort(buff, low, index);
	do_QuickSort(buff, index + 1, high);
}

int QuickSort(int *buff, int buff_len)
{
	if (buff == NULL || buff_len <= 0)
	{
		return PARAMETER_ERROR;
	}

	do_QuickSort(buff, 0, buff_len - 1);
	return 0;
}

int ReverseOrder(int *buff, int buff_len)
{
	int i = 0;
	int tmp_data = 0;

	if (buff == NULL || buff_len <= 0)
	{
		return PARAMETER_ERROR;
	}

	for (i = 0; i < buff_len / 2; i++)
	{
		tmp_data = buff[i];
		buff[i] = buff[buff_len - 1 - i];
		buff[buff_len - 1 - i] = tmp_data;
	}

	return 0;
}
